package main

import (
	"fmt"
	"math"
)

/*
若干个色块排成一排，有色块有两种颜色R和G，你可以喷漆，将颜色互换
要使R都在G的左边，例如RRGGGG，最少需要几次喷漆动作
*/
func dpPainting(str string) int {
	n := len(str)
	var min int = math.MaxInt64
	var dp [][]int
	dp = append(dp, make([]int, n+1))
	dp = append(dp, make([]int, n+1))

	for i := 1; i <= n; i++ {
		dp[0][i] = dp[0][i-1]
		if str[i-1] == 'G' {  //i的含义是界限的右边位
			dp[0][i] += 1
		}
	}
	for j := n-1; j >= 0; j-- {  //dp[0][0]和dp[1][n]都必为0
		dp[1][j] = dp[1][j+1]
		if str[j] == 'R' {
			dp[1][j] += 1
		}
	}
	fmt.Println(dp)

	for i := 0; i < n; i++ {
		min = Min(min, dp[0][i]+dp[1][i])
	}
	return min
}

func dpPaintingV2(str string) int {
	n := len(str)
	var min int = math.MaxInt64
	var R []int = make([]int, n+1)

	for j := n-1; j >= 0; j-- {  //dp[0][0]和dp[1][n]都必为0
		R[j] = R[j+1]
		if str[j] == 'R' {
			R[j] += 1
		}
	}
	fmt.Println(R)

	var G int
	for i := 0; i < n+1; i++ {
		if i-1 >= 0 && str[i-1] == 'G' {  //i的含义是界限的右边位
			G++
		}
		min = Min(min, G+R[i])
	}
	return min
}

func dpPaintingV3(str string) int {
	n := len(str)
	var min int = math.MaxInt64
	var R int
	var G int	

	for j := n-1; j >= 0; j-- {  //dp[0][0]和dp[1][n]都必为0
		if str[j] == 'R' {
			R += 1
		}
	}

	for i := 0; i < n+1; i++ {
		fmt.Print(R, " ")
		if i-1 >= 0 && str[i-1] == 'G' {  //i的含义是界限的右边位
			G++
		}
		min = Min(min, G+R)
		if i <= n-1 && str[i] == 'R' {  //这种做法是真牛逼，两个数组全省了，就用两个int，牛逼。完全动态无记忆
			R--
		}
	}
	return min
}

func Min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	fmt.Println(dpPaintingV3("RGRRRRGGGRGRGRRRGGGGGGGGRG"))
	fmt.Println(dpPaintingV3("GRGGGGRG"))
	fmt.Println(dpPaintingV3("RRGGGGGG"))
}